package leetcode.editor.cn;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution652 {

    Map<String, Integer> map = new HashMap<String, Integer>();
    LinkedList<TreeNode> res = new LinkedList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        helper(root);
        return res;
    }

    public String helper(TreeNode root){
        if (root == null) return "#";
        String left = helper(root.left);
        String right = helper(root.right);

        String rootString = left + "," + right + "," + root.val;

        int rootSize = map.getOrDefault(rootString, 0);
        if (rootSize == 1){
            res.add(root);
        }
        map.put(rootString, rootSize+1);
        return rootString;
    }
}
